package Solution.problem094.BinaryTree;

import common.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @program Leetcode
 * @description: 二叉树非递归前序遍历
 * @author: lishangsheng
 * @create: 2019/07/08 11:46
 */
public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        return preOrderNonRecursive(root);
    }

    /**
     * 非递归实现方式
     * @param root
     * @return
     */
    public List<Integer> preOrderNonRecursive(TreeNode root) {
        List<Integer> values=new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (true) {
            while (root != null) {
                values.add(root.val);
                stack.push(root);
                root = root.left;
            }
            if (stack.isEmpty())
                break;
            root = stack.pop();
            root = root.right;
        }
        return values;
    }


    /**
     * 递归实现方式
     * @param root
     * @param tree
     */
    public void inorder(TreeNode root, ArrayList<Integer> tree){
        if(root != null){
            inorder(root.left, tree);
            tree.add(root.val);
            inorder(root.right, tree);
        }
    }
}


